package 算法.leetcode.labuladong.数组和链表;

import 算法.leetcode.offer.base.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/6/18
 */
public class 链表中下一个更大的节点 {
    class Solution {
        public int[] nextLargerNodes(ListNode head) {
            // 先将链表放入数组中
            List<Integer> list = new ArrayList<>();
            for (;head!=null;head= head.next){
                list.add(head.val);
            }
            // 定义一个单调栈
            int[] ans = new int[list.size()];
            Stack<Integer> stack = new Stack<>();
            for (int i = list.size()-1;i>=0;i--) {
                while (!stack.isEmpty()&& stack.peek()<list.get(i)){
                    stack.pop();
                }
                ans[i] = stack.isEmpty()?0:stack.peek();
                stack.push(list.get(i));
            }
            return ans;
        }
    }
}
